The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


The sequence of y0 values for 256-bit keys is

q1[q0[q0[q1[q1[i] ⊕ k3] ⊕ k2] ⊕ k1] ⊕ k0]

where the kj are different bytes from Me. Smaller keys result in similar equations with fewer key bytes, so the analysis is almost identical. The question at hand is whether two distinct sets of four key bytes can result in an identical sequence of 20 y0 values. In fact, we exclude the input and output whitening values to concentrate solely on the round subkeys, so only 16 values are included in our test (one per round). Clearly, there are 232 such sequences. However, this number can be reduced for the purposes of our search by noting that, since the “outer” mapping q1 is bijective, it can be removed from the equation, leaving us with

q0[q0[q1[q1[i] ⊕ k3] ⊕ k2] ⊕ k1] ⊕ k0

Now the outer XOR term k0 can be effectively removed by creating a related sequence with only 15 values, where the y0 values for i = 5, ..., 19 are XORed with the i = 4 value. The k0 terms thus cancel out, so there are only 224 equivalence classes of sequences, speeding up the search dramatically. If all these sequences (each with 15*8 = 120 bits) are unique, then the y0 sequence is also guaranteed to be unique.

For 192-bit keys, the y0 sequence is

q1[q0[q0[q1[i] ⊕ k2] ⊕ k1] ⊕ k0] ⊕k0]

and for 128-bit keys, it is

q1[q0[q0[i] ⊕ k1] ⊕ k0]

In a manner identical to that discussed for 256-bit keys, the outer q1 permutation can be removed for these smaller keys, and the outer k0 term can similarly be removed by creating the related XOR sequence. The number of the remaining sequences is 216 and 28, respectively. All these sequences can then be compared across key sizes (with a total of NS = 224 + 216 + 28 sequences) to verify uniqueness.

A computer search has been performed over y0, y1, y2 and y3, for all sequences across all key lengths. It turns out that only 64 bits of each sequence were sufficient to distinguish the sequences. This fact is actually quite encouraging, since there are 120 bits in each sequence, giving some heuristic comfort that the sequences are in fact quite different. Each search requires slightly more than 128 MB of memory (i.e., 8Ns bytes) to hold all the sequences, which are then sorted and compared to adjacent values to guarantee uniqueness. The test was run on a Pentium computer with only 32 MB of memory, so the search was actually performed in multiple passes, running through all the Ns values several times, on each pass selecting only those values falling into certain bins. For example, using approximately 8 MB of memory, there are 16 passes, with the mth pass discarding all sequence values for which a fixed 4-bit field of the sequence does not equal to m.

Similar arguments apply to the Bi sequence, and the same empirical verification has been performed for both sequences. Note that, since the operations used to compute K2i and K2i+1 from Ai and Bi are reversible, proving that the Ai and Bi sequences are distinct is more than sufficient to prove that the Kj sequences are distinct.

The definitive result from these tests is that there are no two distinct keys of any size for which the same sequence of Ai and Bi values is obtained. Thus, the round subkey sequence Kj is unique across keys.

8.2 Controlling Changes in Round Subkeys

In a related-key attack, one is concerned about introducing controlled differences into key material that will produce predictable effects that depend on the pair of keys. The basic intuition is that if one can observe the difference in behavior produced by two keys known to have a particular mathematical difference, then one might be able to discern information about the true value of the two keys. Normally one does not limit the attack to pairs of keys and instead may consider subsets of keys instead. Either way, this is a natural attack in many environments where multiple encryption keys are used which are not truly independent of each other.

One very natural notion of mathematical difference is the XOR difference of two values. In this section we consider the problem of trying to produce two sequences of round subkeys {Ki} and {i} that have a desired difference (either additive or XOR). Recall that the Ki (and i) are computed as a function of the sequences A and B (respectively and ). Therefore we consider the problem of trying to produce two sequences A = {Ai} and = {i} such that individual elements have a desired difference δi = Aii (a similar discussion holds for B = {Bi}). A and B are generated using four 8-bit, key-dependent S-boxes in parallel followed by multiplication by a 4-by-4 MDS matrix over GF(28), where each S-box output is treated as one component of a four-dimensional vector over GF(28). Due to the linearity of the MDS matrix multiply, it is very natural to consider attacks that introduce XOR differences between A and , since it is very easy to pass XOR differences through the MDS matrix.

8.2.1 XOR Difference Sequences in A and B

Let A and be sequences for two keys M and respectively. If we have a specific difference sequence, δ = {δi}, we want to see in A (i.e., δi Aii), we are faced with an interesting problem: since the MDS matrix multiply is XOR-linear, each desired output XOR from the matrix multiply uniquely determines the input XOR. This means that:

1.  Any input difference δIi to the MDS matrix corresponds to an output difference for each of the four S-boxes. Hence a difference sequence δ induces four XOR-difference sequences δj for the four S-boxes. For any difference sequence δj = {δji}, each value is an 8-bit value instead of a 32-bit value. As a result, we will sometimes refer to these sequences as difference byte sequences.
2.  The zero sequence δ can occur only when each difference byte sequence δj is the zero sequence.
3.  Only 1020 possible output differences (out of the 232) in δi can occur with a single “active” (altered) S-box (i.e., only one δj is a non-zero sequence). Most differences require all four S-boxes to be active and hence all δj to be non-zero sequences.

The above analysis is of course also valid for the B sequence.

Given that any desired difference sequence δ corresponds to four difference byte sequences δj, we need to examine the properties of the S-boxes to determine the difficulty of generating specific δj.


Previous Table of Contents Next